'''
https://leetcode.cn/problems/number-of-islands-ii/description/?envType=study-plan-v2&envId=premium-algo-100
'''
from typing import List


class UF:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = 0

    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]

    def is_same_set(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx != fy:
            self.father[fy] = fx
            self.sets -= 1


class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        def idx(x, y):
            return y + x * n

        res = [0] * len(positions)
        total_grid = m * n
        uf = UF(total_grid)

        visited = [[False] * n for _ in range(m)]
        for i, (x, y) in enumerate(positions):
            if not visited[x][y]:
                visited[x][y] = True
                uf.sets += 1
                for tx, ty in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                    if 0 <= tx < m and 0 <= ty < n and visited[tx][ty]:
                        uf.union(idx(tx, ty), idx(x, y))
            res[i] = uf.sets
        return res
